package ai.zixing.mashibing.basic_class.class12;

import java.util.HashMap;

/**
 * 给定一个字符串str，给定一个字符串类型的数组arr。
 * arr里的每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来。
 * 返回需要至少多少张贴纸可以完成这个任务。
 * 例子：str= "babac"，arr = {"ba","c","abcd"}
 * 至少需要两张贴纸"ba"和"abcd"，因为使用这两张贴纸，把每一个字符单独剪开，
 * 含有2个a、2个b、1个c。是可以拼出str的。所以返回2。
 */
public class Code02_StickersToSpellWord {

    public static int minSticker1(String[] stickers, String target) {
        int n = stickers.length;
        // 代表所有贴纸，替代原始 stickers
        int[][] map = new int[n][26];
        HashMap<String, Integer> dp = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char[] str = stickers[i].toCharArray();
            for (char c : str) {
                map[i][c - 'a']++;
            }
        }
        dp.put("", 0);
        return process1(dp, map, target);
    }

    // dp 缓存
    // map 原始贴纸
    // rest 剩余的目标，唯一的可变参数
    // 返回-1，表示map中的贴纸，搞不定 rest
    public static int process1(HashMap<String, Integer> dp, int[][] map, String rest) {
        if (dp.containsKey(rest)) {
            return dp.get(rest);
        }
        // 正式的递归调用过程
        // ans -> rest 使用最少得贴纸数量
        int ans = Integer.MAX_VALUE;
        // n 种贴纸
        int n = map.length;
        // 去替代 rest
        int[] tmap = new int[26];
        char[] target = rest.toCharArray();
        for (char c : target) {
            tmap[c - 'a']++;
        }
        // map 去搞定 tmap
        for (int i = 0; i < n; i++) {
            // 保证当前贴纸只是包含 target 中的一种字符
            // 如 target = "asdf", 而贴纸是 "xyz"，应该之间跳过
            if (map[i][target[0] -'a'] == 0) {
                continue;
            }
            // sb -> i号贴纸用到的字符都去掉了，剩余的字符
            StringBuilder sb = new StringBuilder();
            // i 贴纸， j 枚举 a-z 字符
            for (int j = 0; j < 26; j++) {
                // j 字符是 target 需要的
                if (tmap[i] > 0) {
                    for (int k = 0; k < Math.max(0, tmap[j] - map[i][i]); k++) {
                        sb.append((char) ('a' + j));
                    }
                }
            }
            String s = sb.toString();
            int tmp = process1(dp, map, s);
            if (tmp != -1) {
                ans = Math.min(ans, tmp + 1);
            }
        }
        dp.put(rest, ans == Integer.MAX_VALUE ? -1 : ans);
        return dp.get(rest);
    }

    public static void main(String[] args) {
        String[] arr = {"aaaa", "bbaa", "ccddd"};
        String str = "abcccccdddddbbbaaaaa";
        System.out.println(minSticker1(arr, str));
    }
}
